In this paper, we combine a novel Sequential Graph Coloring Heuristic Algorithm (SGCHA) with a non-systematic method based on a cultural algorithm to solve the graph coloring problem (GCP). The GCP involves finding the minimum number of colors for coloring the graph vertices such that adjacent vertices have distinct colors. In our solving approach, we first use an estimator which is implemented with SGCHA to predict the minimum colors. Then, in the non-systematic part which has been designed using cultural algorithms, we improve the prediction. Various components of the cultural algorithm have been implemented to solve the GCP with a self adaptive behavior in an efficient manner. As a result of utilizing the SGCHA and a cultural algorithm, the proposed method is capable of finding the solution in a very efficient running time. The experimental results show that the proposed algorithm has a high performance in time and quality of the solution returned for solving graph coloring instances taken from DIMACS website. The quality of the solution is measured here by comparing the returned solution with the optimal one.

In this paper we investigate the performance of Cultural Algorithms over the complete range of system complexities, from fixed to chaotic.In order to apply the Cultural Algorithm over all complexity classes we generalize on its co-evolutionary nature to keep the variation in the population across all complexities. Based on previous cultural algorithm approaches, we were to extend the existing models to produce a more general one that could be applied across all complexity classes. We produced a new version of the Cultural Algorithms Toolkit, CAT 2.0, which supported a variety of co-evolutionary features at both the Knowledge and Population levels. We then applied the system to the solution of a 150 randomly generated problems that ranged from simple to chaotic complexity classes. As a result we were able to produce the following conclusions: No homogeneous Social Fabric tested was dominant over all categories of complexity. As the complexity of problems increased, so did the complexity of the Social Fabric that was need to deal with it efficiently. In other words, there was experimental evidence that social structure can be related to the frequency and complexity type of the problems that presented to a cultural system.